package nowCoder;

/**
 * Created by Ghost on 2015/3/27.
 * 给定一个单链表的头部节点head，链表长度为N。
 * 如果N为偶数，那么前N/2个节点算作左半区，后N/2个节点算作右半区；
 * 如果N为奇数，那么前N/2个节点算作左半区，后N/2+1个节点算作右半区；
 * 左半区从左到右依次记为L1->L2->...，右半区从左到右依次记为R1->R2->...。
 * 请将单链表调整成L1->R1->L2->R2->...的样子。
 * 例如： 1->2->3->4 调整后：1->3->2->4 1->2->3->4->5 调整后：1->3->2->4->5
 * 要求：如果链表长度为N，时间复杂度请达到O(N)，额外空间复杂度请达到O(1)
 */
public class ReformList {
    public void relocateList(ListNode head) {
        if(head==null || head.next==null)
            return;
        ListNode faster = head,lower = head;
        ListNode lowerpre = null;
        while(faster.next!=null){
            lowerpre = lower;
            lower = lower.next;
            faster = faster.next;
            if(faster.next!=null)
                faster = faster.next;
        }

        ListNode head2 = lower;
        ListNode head1 = head;
        lowerpre.next = null;
        while(head1!=null && head2!=null){
            ListNode tmp2 = head2.next;
            head2.next = head1.next;
            head1.next = head2;
            head1 = head2.next;
            head2 = tmp2;
        }
        if(head2!=null){
            ListNode h = head;
            while(h.next!=null){
                h = h.next;
            }
            h.next = head2;
        }
    }
    public static void main(String[] args){
        ReformList reformList = new ReformList();
        ListNode head = new ListNode(1);
        reformList.relocateList(head);
        while(head!=null){
            System.out.println(head.val);
            head = head.next;
        }
    }
}
